#include <iostream>
#include <vector>
#include <string>
using namespace std;

class BitwiseParenthesis {
public:
    // 更高效的位运算方法
    vector<string> generateParenthesis(int n) 
    {
        vector<string> result;
        // 使用整数来跟踪括号状态
        generate(0, 0, 0, n, result);
        return result;
    }
    
private:
    void generate(int pos, int open, int close, int n, vector<string>& result) 
    {
        if (pos == 2 * n) {
            result.push_back(buildString(open | close, 2 * n));
            return;
        }
        
        // 可以添加左括号的条件
        if (countBits(open) < n) 
        {
            generate(pos + 1, open | (1 << (2 * n - pos - 1)), close, n, result);
        }
        
        // 可以添加右括号的条件：右括号数量小于左括号数量
        if (countBits(close) < countBits(open)) 
        {
            generate(pos + 1, open, close | (1 << (2 * n - pos - 1)), n, result);
        }
    }
    
    // 计算二进制中1的个数
    int countBits(int x) 
    {
        int count = 0;
        while (x) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
    
    // 从位模式构建字符串
    string buildString(int pattern, int length) 
    {
        string result;
        int mask = 1 << (length - 1);
        
        for (int i = 0; i < length; i++) 
        {
            if (pattern & mask) 
            {
                result += ')';
            } 
            else 
            {
                result += '(';
            }
            mask >>= 1;
        }
        
        return result;
    }
};

// 迭代版本使用位运算
class IterativeSolution 
{
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> result;
        
        // 遍历所有可能的位模式
        for (int i = 0; i < (1 << (2 * n)); i++) 
        {
            if (isValidPattern(i, n)) 
            {
                result.push_back(patternToString(i, 2 * n));
            }
        }
        
        return result;
    }
    
private:
    bool isValidPattern(int pattern, int n) 
    {
        int balance = 0;
        int leftCount = 0;
        
        for (int i = 2 * n - 1; i >= 0; i--) 
        {
            bool isRight = pattern & (1 << i);
            
            if (isRight) 
            {
                balance--;
                if (balance < 0) return false;
            } 
            else 
            {
                balance++;
                leftCount++;
                if (leftCount > n) return false;
            }
        }
        
        return balance == 0;
    }
    
    string patternToString(int pattern, int length) 
    {
        string result;
        for (int i = length - 1; i >= 0; i--) 
        {
            result += (pattern & (1 << i)) ? ')' : '(';
        }
        return result;
    }
};